package com.atguigu.tree.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
/*
* 赫夫曼编码
*
*
*
* */
/**
 * @author RuiKnag
 * @create 2021-05-19-15:15
 */
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int[] arr={13,7,8,3,29,6,1};
        Node root = huffmanTree(arr);
        preList(root);

    }
    //前序遍历
    public static void preList(Node root){
        if(root==null){
            System.out.println("空树");
        }else {
            root.preList();
        }
    }

    //创建我们的哈夫曼树
    public static Node huffmanTree(int[] arr){
        //创建一个ArrayList存放这些节点
        ArrayList<Node> list = new ArrayList<>();
        //我们首先将数组的值添加到节点中，并存放到列表中
        for(int i=0;i<arr.length;i++){
            list.add(new Node(arr[i]));
        }
        while (list.size()>1){
            //将我们的列表中的数据进行从小到大排序
            Collections.sort(list);
            //取出最小的两个节点
            Node leftNode=list.get(0);
            Node rightNode=list.get(1);
            //构建我们的父节点
            Node parent=new Node(leftNode.val+rightNode.val);
            //将这个两个节点和父节点构成一颗二叉树
            parent.left=leftNode;
            parent.right=rightNode;
            //将父节点存放到列表中，同时删除最小的两个节点
            list.add(parent);
            list.remove(leftNode);
            list.remove(rightNode);
        }
        return list.get(0);


    }
}
//创建节点
//实现Conparable接口
class Node implements Comparable<Node>{
    int val;//节点权值
    Node left;//指向左子节点
    Node right;//指右左子节点

    public Node(int val) {
        this.val = val;
    }
    //前序遍历展示该哈夫曼树
    public void preList(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preList();
        }
        if(this.right!=null){
            this.right.preList();
        }

    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        //从小到达排序
        return this.val-o.val;
    }
}
